package com.frx.datastruct.chaptertwo;
/**
 * 封装一个动态数组类   数组开辟空间时的默认值为0
 * */
public class Array<E> {
    private E[] data;
    /** 数组的实际大小 */
    private int size;

    /** 构造函数传递数组初始的容量大小*/
    public Array(int capacity){
        //java类型不支持直接构造泛型的数组，
        // 所以此处采用先new一个Object类型的数组然后再强转为泛型数组
        data = (E[]) new Object[capacity];
        size = 0;
    }
    /** 将一个数组转换为动态数组的构造方法*/
    public Array(E[] arr){
        data = (E[])new Object[arr.length];
        for (int i = 0; i<arr.length;i++){
            data[i] = arr[i];
        }
        size = arr.length;
    }

    /** 无参构造方法  默认初始容量为*/
    public Array(){
        this(10);
    }

    /** 交换两个索引对应的值*/
    public void swap(int i,int j){
        if (i < 0 || i >= size || j < 0 || j >= size){
            throw new IllegalArgumentException("Index is illegal !");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /** 获取数组中的元素个数*/
    public int getSize(){
        return size;
    }

    /** 获取数组中的容量 */
    public int getCapacity(){
        return data.length;
    }

    /** 判空 */
    public boolean isEmpty(){
        return size == 0;
    }

    /** 向所有元素的后面添加一个元素 */
    public void addLast(E e){

/*        // 如果数组满了，再向其中添加元素，抛异常 (初始逻辑)
        if(size == data.length){
            throw new IllegalArgumentException("AddLast failed,Array is full.");
        }
        data[size] = e;
        size ++;*/

        //更改为复用add的逻辑
        add(size,e);
    }

    /** 在所有数组的前面添加一个元素 */
    public void addFirst(E e){
        add(0,e);
    }

    /** 在指定的index位置插入一个元素e */
    public void add(int index,E e){


        // 校验索引 index 的合法性
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed,Require index >=0 and index < size");
        }
/*      原静态数组的逻辑，如果大于数组长度，抛出异常
        if(size == data.length){
            throw new IllegalArgumentException("Add failed,Array is full");
        }
*/
        // 动态数组的新实现，满了进行扩容的操作
        if(size == data.length){
            resize(2*data.length);
        }

        // index 之后的元素需要向后移动一位
        for (int i = size -1 ; i >= index; i--){
            //每个元素向后移动一位
            data[i+1] = data[i];
        }
        data[index] = e;

        //最后维护size的长度
        size ++;
    }

    /** 获取index位置元素的方法 */
    public E get(int index){
        //参数合法性校验
        if(index <0 || index > size){
            throw new IllegalArgumentException("get failed,index is illegal");
        }
        return data[index];
    }

    /** 获得最后一个元素的方法 */
    public E getLast(){
        return get(size - 1);
    }

    /** 获得第一个元素的方法 */
    public E getFirst(){
        return get(0);
    }



    /** 更新index位置的方法 */
    public void set(int index,E e){
        // 参数合法性校验
        if(index <0 || index > size){
            throw new IllegalArgumentException("set failed,index is illegal");
        }
        data[index] = e;
    }

    /** 数组是否包含某个元素的方法 */
    public boolean contains(E e){
        for (int i=0;i<size;i++){
            //此处改为类对象，用值比较而不是引用比较
            if (data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    /** 返回数组中某个元素对应的索引的方法 如果数组中不存在该元素返回 -1 */
    public int find(E e){
        for (int i = 0;i < size; i ++){
            if (data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    /** 删除数组中某个位置元素的方法，并且返回该元素的值 */
    public E remove(int index){

        if (index < 0 || index > size){
            throw new IllegalArgumentException("remove fail,index is illegal");
        }
        E ret = data[index];
        // 执行删除操作，该元素后面的元素向前覆盖
        for(int i = index + 1; i < size; i++){
            data[i-1] = data[i];
        }
        // 最后要维护size的值
        size --;
        //将size处不会被引用到的对象引用标记为null,等待垃圾回收机制回收
        //loitering(闲逛的，闲散的) object ！= memory leak
        data[size] = null;

        /*进行一个缩容的操作
        * 考虑到频繁的对最后一个元素进行添加和删除会使添加和删除操作的时间复杂度为O(n)
        * 因此对缩容进行了优化
        * */
        if(size == data.length/4 && data.length/2 != 0){
            resize(data.length/2);
        }
        return ret;
    }

    /** 删除第一个元素 */
    public E removeHead(){
        return remove(0);
    }

    /** 删除最后一个元素 */
    public E removeLast(){
        return remove(size-1);
    }

    /** 从数组中删除元素e */
    public void removeElement(E e){
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    /** 重写toString方法 */
    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size=%d , capacity = %d\n",size,data.length));
        res.append('[');
        for (int i = 0; i<size;i++){
            res.append(data[i]);
            if (i != size-1){
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }

    /**  数组扩容的操作 */
    public void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0;i < size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}
